1. Field of the Invention
This invention relates to a technology for expanding compressed moving picture data, more specifically to a technology for effectively accessing a cache memory when expansion processing of moving picture data is executed by software.
2. Description of the Related Art
As a method of compression and expansion for storing and transmitting high quality moving picture data, an international standard method called the MPEG (Moving Picture coding Experts Group) is established. Since an enormous amount of calculation is required for expanding compressed moving picture data to real time data in conformity with the standard of the MPEG, specifically designed hardware has been conventionally used. However, due to the recent improvement in the performance of a microprocessor, it is becoming possible to realize the expansion of compressed moving picture data by software alone using an ordinary microprocessor.
Describing the expansion algorithm of the MPEG roughly, it consists of decoding processing of variable-length codes, reverse quantization processing, reverse discrete cosine transformation processing and motion compensation processing.
An MPEG expansion apparatus will be described for an example composed by a combination of a system with a CPU 401 as a core part and software on the CPU 401 as shown in FIG. 4.
A bit stream compressed by the MPEG is stored in an external storage 404. The bit stream is read out from the external storage 404 such as a CD-ROM and temporarily stored in a memory 402. The bit stream stored in the memory 402 is expanded by the function of decoding software operating on the CPU 401 and expanded picture data is stored in the memory 402. The picture data stored in the memory 402 is converted to a display format by software operating on the CPU 401 and transferred to a display 403. The decoding software is stored in advance in an external storage such as a floppy disc (FD) 407.
FIG. 5 shows an order of picture frames when an compression and an expansion are performed with the MPEG. The MPEG has three picture types for coding one frame of picture, namely the I picture, the P picture and the B picture. The I picture is of a picture type to be compressed using only information within the frame without any motion compensation processing performed. The P picture is of a picture type on which motion compensation processing is performed in that the frame is estimated from picture information of frames older than the frame. The B picture is of a picture type on which motion compensation processing is performed in that a picture signal of the frame is bi-directionally estimated from picture information of both frames older than the frame and future frames.
FIG. 5(A) shows an assignment of typical picture types when a moving picture is compressed with the MPEG. A Frame #1 is an I picture and is compressed without reference to picture information of other frames. A frame #2 is a B picture and is compressed by bi-directional motion compensation processing using the frame #1 and a frame #4. A frame #3 is also a B picture and is compressed by bi-directional motion compensation processing with reference to the frame #1 and the frame #4. The frame #4 is a P picture and is compressed by motion compensation processing using the frame #1. A frame #5 is a B picture and is compressed by bi-directional motion compensation processing using the frame #4 and a frame #7. A frame 6 is a B picture and is compressed by bi-directional motion compensation processing using the frame #4 and the frame #7. The frame #7 is a P picture and is compressed by motion compensation processing with reference to the frame #4. Arrows denoted by dotted lines show the reference relationship among the frames.
FIG. 5(B) shows a processing order of each frame when a compression and an expansion are performed in accordance with the above mentioned picture types. Before executing compression processing, input moving picture signals are realigned from the state of FIG. 5(A) to the state of FIG. 5(B).
The frame #1 being an I picture is compressed in the first place with the MPEG. Then the frame #4 being a P picture is compressed with reference to a local decoding picture of the frame #1. The frame #2 being a B picture is then compressed with reference to local decoding pictures of the frame #1 and the frame #4. The frame #2 being a B picture is compressed with reference to local decoding pictures of the frame #1 and the frame #4. The frame #3 being a B picture is compressed with reference to local decoding pictures of the frame #1 and the frame #4. The frame #7 being a P picture is compressed with reference to a local decoding picture of the frame #4. Following this, the frame #5 is compressed with reference to local decoding pictures of the frame #4 and the frame #7. The frame 6 is compressed with reference to local decoding pictures of the frame #4 and the frame #7.
Information of each frame is described in the order of compression of the frames in a MPEG bit stream describing the compressed pictures. That is to say, an order of frames to be input in an expander is different from an original order of moving picture frames.
When the MPEG bit stream compressed as above is expanded, the frame #1 is expanded first. Then the frame #4 (P picture) is expanded with reference to the picture of the expanded frame #1. The frame #2 (B picture) is expanded with reference to the two pictures of the expanded frame #1 and the expanded frame #4. The frame #3 (B picture) is expanded with reference to the two pictures of the expanded frame #1 and the expanded frame #4. The frame #7 (P picture) is expanded with reference to the picture of the expanded frame #4. Following this, the frame #5 is expanded with reference to the two pictures of the expanded frame #4 and the expanded frame #7. The frame #6 is expanded with reference to the two pictures of the expanded frame #4 and the expanded frame #7. FIG. 5(C) shows an order for displaying the expanded pictures on a display 403 of FIG. 4.
Decoding software, i.e. an operation by a program stored in a floppy disc of FIG. 4 will now be described with reference to a flow chart of FIG. 1.
In expansion processing of one frame, steps of a variable-length code decoding (step 102), a reverse quantization (step 103), a reverse DCT (step 104) and a motion compensation (step 105) are repeated for each macro block and, when the last macro block of one frame is processed, the expansion processing of one frame is finished (step 107). Further, the motion compensation processing (step 105) is not performed for an I picture. In addition, in the motion compensation processing (step 105), a one way motion compensation estimation is performed for a P picture and bi-directional motion compensation processing is performed for a B picture.
The variable-length code decoding (step 102) of one macro block reads out the bit stream stored in the memory 402 and decodes the Huffman code by referring to the variable-length code table for every few bits. Then, a pointer pointing a location on the memory stores a position where the bit stream was read out. The pointer is advanced for a read out amount every time the bit stream is read out and always points a location of a bit stream to be read out. The variable-length code table used here is stored in the FD 407 in advance together with the decoding software and is read into the CPU when the variable-length code decoding processing is carried out. A decoding result of the Huffman code is stored in a region on the memory 402 which is called a DCT coefficient buffer.
The reverse quantization (step 103) is processing for calculating the product of a value stored in the DCT coefficient buffer and a quantization parameter included in the MPEG bit stream. A result of the reverse quantization is written back to the above mentioned DCT coefficient buffer.
The reverse DCT (step 104) performs the two dimensional reverse discrete cosine transformation on the reverse quantized value stored in the DCT coefficient buffer. A result of the two dimensional reverse discrete cosine transformation is written back to the same DCT coefficient buffer.
The motion compensation (step 105), which utilizes the temporal redundancy of a moving picture, is processing for cutting out a portion of a picture from the already expanded frame to decode a picture. The position of the picture to be cut out is determined by a parameter (which is stored in the MPEG bit stream as well) called a motion vector. The region to be cut out is a square region called a macro block consisting of vertical 16 pixels and horizontal 16 pixels. With the cut out region added to the result of the reverse DCT stored in the DCT coefficient buffer, the expansion of the macro block is completed. The expanded macro block is stored in the memory 402.
In a system as shown in FIG. 4, a cache memory 405 is usually built in the CPU 401. The cache memory is a memory that is smaller in volume but can be accessed faster than an ordinary memory. Data of the memory 402 that the CPU 401 accessed recently is stored in the cache memory. Contents that have not been accessed for a long time since the last access are controlled so that they are excluded from the cache memory and written back in the memory 402.
That is to say, since data the CPU has accessed once is left in the cache memory so long as it is accessed right thereafter, it can be accessed again within the machine cycle of the CPU. This is called a cache hit. However, when accessing data which has not been accessed at all or that has excluded from the cache memory to the memory because it has not been accessed for a long time since it was accessed once, it take a few times or scores of times of the machine cycle of the CPU. This phenomenon is called a cache mistake. When a cache mistake occurs, processing speed of software is slowed because a processor has to read data from a memory. Therefore, it is important to make the probability of a cache mistake occurrence as low as possible in order to increase the processing speed of the software.
The volume of a cache memory built in a microprocessor that is currently available is several tens of kilobyte at the maximum. A secondary cache memory may be disposed outside the CPU 401 depending on the structure of a system. The volume of the secondary cache memory is larger than the volume of the cache memory built in the CPU. In general, the volume of the secondary cache memory is several hundreds of kilobyte at the maximum. Whereas, the volume of one frame of a picture to be handled with the MPEG may range from several tens of kilobyte to a few megabyte depending on a screen size. In the case of a standard called the MPEG 2 main profile/main level that is most generally used at present, a picture of one frame only can be stored in the secondary cache memory at most because the volume of one frame is several hundreds of kilobyte.
A behavior of the cache memory when an expansion of the MPEG 2 main profile/main level is carried out in a conventional expansion apparatus will now be described. For example, a series of actions for expanding the frame #2 of FIG. 5(B) and then expanding the frame #3 are described.
In motion compensation processing during the expansion processing of the frame #2, it is necessary to access picture for three frames in conjunction with a picture of the frame #2 to be expanded because the frame #1 and the frame #4 are referred to. Only parts of the frame #1, the frame #4 and the frame #2 respectively are stored in the cache memory when the expansion processing of the frame #2 is finished, since the picture for three frames cannot be stored in the cache memory. Since the expansion algorithm of the MPEG proceeds with the processing downward from the left to the right of the screen, in many cases, a frame to be referred to is accessed from the upper end to the lower end on the screen in order. Therefore, with the progress of the expansion processing, data in the area close to the upper end of the screen is excluded from the cache memory and data in the area close to the lower end is ultimately left in the cache memory.
Consequently in the motion compensation processing of the processing for expanding the frame #3, the frame #1 and the frame #4 are referred to again. When the area close to the upper end of the screen of the frame #3 is expanded, the areas close to the upper ends of the frame #1 and the frame #4 are to be referred to, but, since only data in the areas close to the lower ends of the frame #1 and the frame #4 is left in the cache memory as a result of the expansion processing of the frame #2, all the accesses causes a cache mistake. Further, since data in the areas close to the lower ends of the frame #1 and the frame #4 left in the cache memory are excluded when the expansion processing of the areas close to the upper ends are carried out, all the accesses even in the processing for expanding the area close to the lower end of the screen of the frame #3 cause a cache mistake.
As described in the preceding paragraphs, since the entire frame to be referred to in the motion compensation processing cannot be stored in the cache memory in the conventional moving picture expansion apparatus, cache mistakes frequently take place. Due to the frequent occurrence of cache mistakes, an identical reference frame must be read from the memory many times especially when a plurality of frames adjacent to each other are B pictures and, as a result, the speed of the decoding software is slowed down.
As mentioned above, since the cache memory within the CPU cannot be used effectively especially in the expansion processing of a B picture in the conventional moving picture expansion apparatus established with software, the processing speed becomes slow. That is to say, due to a frequent occurrence of cache mistakes, a waiting time for a memory access is a major factor of the reduced speed of the decoding software.
The object of the present invention is to restrain a cache mistake in a motion compensation processing of a B picture and to provide a moving picture expansion technology in which reduced speed of a decoding software is prevented.
When expansion processing of a frame is conducted, it is a B picture and the next frame is a B picture as well, the present invention conducts expansion processing of the adjacent two frames by alternately repeating expansion processing for one macro block of the first frame and expansion processing for one macro block of the second frame.
Further, when expansion processing of a frame is conducted, if it is a B picture and the next frame is a B picture as well, the present invention conducts expansion processing of the adjacent two frames by alternately repeating expansion processing of a fixed number of macro blocks of the first frame and expansion processing of a fixed number of macro blocks of the second frame.
As mentioned above, in the present invention, if both the adjacent two frames are B pictures, since the expansion processing of the two frames are alternately conducted for one macro block or a plurality of macro blocks, the expansion processing of macro blocks in the same positions of the adjacent frames is consecutively executed. In doing so, the probability of a cache mistake occurrence in the motion compensation processing can be reduced. This is based on the characteristics that the motion compensation processing in the macro blocks located in the same positions of the adjacent frames often utilizes the regions in the positions close to them in the reference frames.